package Algorithm.dynamicProgramming.introduct;

import java.util.HashSet;
import java.util.Scanner;

/**
 * 删除字符的最少个数
 * 题目简述：一个字符串s长度为偶数，且当i为偶数时满足s.charAt(i)==s.charAt(i+1)，则s为好字符串。
 * 例如"aabb"、"bbeecc"。问将一个小写字母字符串从中删除一些字符构成好字符串的最少删除数
 */
public class DeleteToGoodStr {

    /**
     * 思路：对于疑似dp的题可以直接强行往dp上套，根据题意定义dp项，然后假定前面的状态，看新增一个元素会对前面的状态有什么影响。
     *
     * 根据题意可知，即求字符串中的最大好串长度，故定义dp[i]为前i个字符的最大好串长度。当遍历到dp[i]时，前i-1个字符的dp[i-1]已定
     * 假设为_x_x__x_x__，x表示已匹配字符，如果i字符要与x及前面的字符配对，则必然要删除已配对的字符，因此只能与x后的字符进行配对
     * 因此可用一个set记录当前最大好串后还未匹配的字符，每遍历一个字符若set中包含对应字符，则dp[i] = dp[i-1] + 2并清空set。否则将其加入到set
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int n = str.length();
        int[] dp = new int[n];
        HashSet<Character> notMatchSet = new HashSet<>();
        notMatchSet.add(str.charAt(0));
        for (int i = 1;i < n;i++) {
            char c = str.charAt(i);
            if (!notMatchSet.contains(c)) {
                dp[i] = dp[i-1];
                notMatchSet.add(c);
            } else {
                dp[i] = dp[i-1] + 2;
                notMatchSet.clear();
            }
        }
        System.out.println(n - dp[n-1]);
    }
}
